import java.util.Scanner;

public class day5 {
    /**
     * NC164 最长上升子序列(二)
     * https://www.nowcoder.com/practice/4af96fa010c44638a7e112abf65f7237?tpId=196&tqId=39285&ru=/exam/oj
     */
    public int LIS (int[] a) {
        // 二分 + 贪心
        // 贪心：
        // 1.不需要关心前面的序列长什么样子，只需要关系长度为 x 的时候的末尾的数据值即可
        // 2.存长度为 x 的所有子序列的时候，只需要存储该长度子序列中 末尾值是最小的那个数即可
        // 二分：
        // 3.二分快速找到要插入的位置

        int n = a.length;
        int[] dp = new int[n + 1]; // dp[i] 表示长度为 i 的末尾的最小值
        int x = 0;
        for(int num : a) {
            if(x == 0 || num > dp[x]) {
                // 刚开始 或者 长度大于最长的长度的末尾的数据，那么就接在这个之后面，另起一个长度++
                dp[++x] = num;
            }else {
                // 二分查找位置
                int l = 1,r = x;
                while(l < r) {
                    int mid = (l + r) / 2;
                    if(dp[mid] >= num) {
                        r = mid;
                    }else {
                        l = mid + 1;
                    }
                }
                dp[l] = num;
            }
        }
        return x;
    }
    public int LIS1 (int[] a) {
        // 动态规划 ---- 这个题的数据太长，不适合
        int n = a.length;
        if(n == 0) {
            return 0;
        }
        int[] dp = new int[n];
        int ret = Integer.MIN_VALUE;
        for(int i = 0;i < n;i++) {
            // 本身的长度最低为1
            dp[i] = 1;
            for(int j = 0;j < i;j++) {
                if(a[i] > a[j]) {
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                    ret = Math.max(ret,dp[i]);
                }
            }
        }
        return ret;
    }



    /**
     * 消减整数
     * https://ac.nowcoder.com/acm/problem/219038
     */
    public static void main2(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();

        while(t-- != 0) {
            int h = in.nextInt();
            int ret = 0;
            int a = 1;
            while(h != 0) {
                h -= a;
                ret++;
                if(h % (a * 2) == 0) {
                    a *= 2;
                }
            }
            System.out.println(ret);
        }
    }



    /**
     * 排序子序列
     * https://www.nowcoder.com/questionTerminal/2d3f6ddd82da445d804c95db22dcc471
     */
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0;i < n;i++){
            arr[i] = in.nextInt();
        }

        int ret = 0;
        int index = 0;
        while(index < n) {
            // 特判一下index为最后一位的时候，这个就是一个子序列
            if(index == n - 1) {
                ret++;
                break;
            }
            if(arr[index] < arr[index + 1]) {
                while(index + 1 < n && arr[index] < arr[index + 1]) {
                    index++;
                }
                // 这个时候 出while循环后，那么就代表一个子序列已经分出来了
                ret++;
            }else if (arr[index] > arr[index + 1]) {
                while(index + 1 < n && arr[index] > arr[index + 1]) {
                    index++;
                }
                ret++;
            }else {
                // 前后值相等，直接过，不算作一个子序列
                while(index + 1 < n && arr[index] == arr[index + 1]) {
                    index++;
                }
            }
            // 这个时候index 在 每一个子序列的最后一位，需要跳出这个子序列
            index++;
        }
        System.out.println(ret);
    }
}
